home *** CD-ROM | disk | FTP | other *** search
-
- /* routines to find best moves */
-
-
- /* General */
-
- /* At first sight it seems easy to look ahead a long way: there
- are only 6 choices for each move and 6^6 (say) is not too big.
- My first attempt looked ahead like this regardlesss of whose
- moves they were, then gave an extra score at the final
- evaluation according to who had the next move. It didn't play
- well. The whose-go score was too crude, and it was unaware of
- promising situations building up on your side: you might have
- ten goes in a row a few moves hence and it would know little of
- it. */
-
- /* So then I tried trying all move sequences ending in loss of
- control as a single move, and then looked ahead 3 or 4 moves.
- It was harder to beat but still not much good unless allowed 10
- minutes per move to think. A little late in the day I
- calculated how many move sequences there might be. If your
- ball-counts are 6 4 2 3 2 1 you have 321 choices of
- move-sequences before lsoing control, and 100 choices happen in
- typical games. */
-
- /* So the current (20.5.91) method is to find the best N
- move-sequences (ie the best looking 1 turn ahead); then for each
- of those look further ahead. At the hardest level it examines
- the results of (up to) 14 "best" moves, 9 replies, 6 moves, 3
- replies, 2 moves, 1 "reasonable" reply. Then it does (the first
- part of) the best of the 14, and if still it's go, repeats. It
- seems to play a pretty mean game */
-
- /* 14.12.91: It was possible to beat this by learning how it
- played. Despite some randomness, it almost always made the same
- mistakes. I tries various alteranatives to the 14,9,6,3,2,1
- scheme. These worked for a while but I soon picked up different
- mistakes (unless it was allowed a long time to think). The
- prehosnt solution to this is to randomise the sequence itself.
- This produces some real variation in its play and I haven't
- beaten it at the hardest level for a quite a while */
-
-
- #include "kalaha.h"
-
-
-
-
-
-
-
-
- /************* STATIC ****************************/
-
- /* these are for looking ahead one complete turn or go. After
- calling find_next_go(), moves[] will contain a sequence of 0-5's
- ending in loss of control. go_results[] contains the initial
- intermediate and final effects of this sequence. nofmoves is
- length of sequence, and complete indicates whether or not it
- does end in loss of control (within find_next_go()). */
-
- /* they are initiallised with go_results[0] containing current
- game, nofmoves = 0, complete = FALSE. */
-
- static char go_results[MAX_MOVES][14];
- static char moves[MAX_MOVES];
- static int nofmoves;
- static BOOL complete;
-
-
-
- /************* FUNCTIONS ********************/
-
- int stupid_move(char * here);
-
- MoveScore best_n_move(int depth, char *here);
-
- static int virtual_move(char * h, char * prev, int p);
-
- static BOOL find_next_go(void);
-
- static void init_go_arrays(char *here);
-
- static int find_best_goes(int n, char *here, char best[MAXBESTGOES][15]);
-
- static int best_1_score(char *here);
-
-
-
- int stupid_move(char * here)
- {
- int i, score, move, state;
- char next[14];
-
- score = here[6] - here[13];
- move = 0;
- for (i=0; i<6; i++)
- {
- int randbit, s;
- if (here[i] == 0) continue;
- randbit = rand() & 1;
- state = virtual_move(next, here, i);
- s = next[6] - next[13];
- if (state == MY)
- s += 2;
- if (s+randbit > score)
- {
- score = s;
- move = i;
- }
- }
- return move;
- }
-
-
- static int cons[] = {1,2,3,6,9,14};
-
- void setup_cons_arr(void)
- {
-
- if (level < 3)
- {
- cons[0] = 1;
- cons[1] = 2;
- cons[2] = 2 + rand()%4;
- cons[3] = 4 + rand()%8;
- return;
- }
- cons[5] = 8 + rand()%12;
- cons[4] = 120/cons[4];
- cons[3] = 4 + rand()%5;
- cons[2] = 21/cons[3];
- cons[1] = 2;
- cons[0] = 1;
- }
-
-
-
- MoveScore best_n_move(int depth, char *here)
- {
- MoveScore temp;
- int num, i, s, consider, randomnumber;
- char next[14];
- char best[MAXBESTGOES][15];
-
-
-
- if (depth<1)
- {
- temp.move = 0; /* irrelavant, stops compiler warning */
- temp.score = best_1_score(here);
- return temp;
- }
-
- /* deal with game over seperately. Its faster, but more important
- find_next_go() makes NO SENSE if no possible moves */
- if (here[0]==0 && here[1]==0 && here[2]==0 && here[3]==0 && here[4]==0 && here[5]==0 )
- {
- temp.move = 0; /* irrelevant */
- temp.score = here[6] - here[13];
- return temp;
- }
-
- setup_cons_arr();
- randomnumber = rand();
-
- consider = cons[depth];
- wassert(consider<MAXBESTGOES);
- num = find_best_goes(consider , here, best);
- wassert(num < 32);
- temp.score = -99999;
- for (i=0; i<num; i++)
- {
- int j, randbit;
- for (j=0; j<14; j++)
- {
- if (j<7)
- next[j] = best[i][j+7];
- else
- next[j] = best[i][j-7];
- }
- randbit = (randomnumber >> i) & 1;
- s = - best_n_move(depth-1, next).score;
- if (s+randbit > temp.score)
- {
- temp.score = s;
- temp.move = best[i][14];
- }
- }
- return temp;
- }
-
-
-
- static int best_1_score(char *here)
- {
- char next[14];
- int i, state, score, j;
-
- /* find the "last" move that gives an extra go or get j = -1 if
- none */
- for (j=5; j>=0; j--)
- {
- int t;
- t = here[j] + j;
- if (t==6 || t==19 || t==32 || t== 45)
- break;
- }
- /* If one exists, this move is done, and function called
- recursively. I think this is a reasonable strategy for weeding
- out a lot of moves if there are a lot. Eg
- 8 0 0 0 0 0
-
- 6 4 2 3 2 1
- has 321 possible move sequences. This strategy finds 28
- including 1st and 4th.
- */
-
-
- score = here[6] - here[13];
- /* NB score cannot get worse so this is default
- in case game over, lower bound otherwise */
-
- for (i=0; i<6; i++)
- {
- int s;
- if (here[i] == 0) continue;
- state = virtual_move(next, here, i);
- if (state == MY && i != j) /* ignore other extra goes */
- continue;
- if (i==j) /* do this one */
- s = best_1_score(next);
- else
- s = next[6] - next[13];
- if (s > score)
- score = s;
- }
- return score;
- }
-
-
-
- static int find_best_goes(int n, char *here, char best[MAXBESTGOES][15] )
- {
- /* make a list in best[] of the n best complete sequnces of moves, or less
- if fewer than n goes. best[i][0-13] contains resulting game positions,
- best[i][14] the first move in sequence.*/
-
-
- int score[MAXBESTGOES];
- int go, nthworst, worstscore, i, s;
-
- init_go_arrays(here);
-
- go = 0;
- while ( find_next_go() )
- {
- if ( go < n )
- {
- score[go] = go_results[nofmoves][6] - go_results[nofmoves][13];
- memcpy( best[go], go_results[nofmoves], 14);
- best[go][14] = moves[0];
- go++;
- }
- else
- {
- nthworst = 0;
- worstscore = score[nthworst];
- for (i=1; i<n; i++)
- {
- if (score[i] < worstscore)
- { nthworst = i; worstscore = score[nthworst]; }
- }
- s = go_results[nofmoves][6] - go_results[nofmoves][13];
- if (s > worstscore)
- {
- memcpy( best[nthworst], go_results[nofmoves], 14);
- best[nthworst][14] = moves[0];
- score[nthworst] = s;
- }
- }
- }
- return go;
- }
-
-
-
-
- static void init_go_arrays(char *here)
- {
- int i;
-
- nofmoves = 0;
- complete = FALSE;
- for (i=0; i<14; i++)
- go_results[0][i] = here[i];
- }
-
-
-
-
- static BOOL find_next_go(void)
- {
- int i, state;
-
- if (complete)
- {
- do /* backtrack */
- {
- nofmoves--;
- if (nofmoves < 0) return FALSE; /* backtracked off beginning */
- i = moves[nofmoves] + 1;
- while (i < 6 && go_results[nofmoves][i] == 0)
- i++;
- }
- while (i >= 6);
- /* backtracked to a point where there's a replacement move */
-
- moves[nofmoves] = i;
- nofmoves++;
- state = virtual_move( go_results[nofmoves], go_results[nofmoves-1], i);
- if (state == MY)
- complete = FALSE;
- }
-
- while (!complete)
- { /* fill up */
- i = 0;
- while (go_results[nofmoves][i] == 0)
- i++;
- wassert(i < 6);
- moves[nofmoves] = i;
- nofmoves ++;
- state = virtual_move( go_results[nofmoves], go_results[nofmoves-1], i);
- if (state != MY)
- complete = TRUE;
- }
-
- return TRUE;
- }
-
-
-
-
- int virtual_move(char * h, char * prev, int p)
- /*
- passed game situation in prev[0...13]. posn p, 0<=p<5, is
- to move.
- 12 11 10 9 8 7
- 13 6
- 0 1 2 3 4 5
-
- If botgo, this maps directly to screen positions, else add 7 mod 14.
- */
- /*
- Returns: MY,YOUR,OVER according to another go, opp's go, game end
- Updates h[] to new values
- */
- {
- int carry, i, temp;
-
- /* virtual move is called ~30K times per move with depth 5,
- consider = 14,9,6,3,2. Following saves >10% compared to memcpy()
- on time to choose move, and allows h==prev */
- h[0] = prev[0]; h[1] = prev[1]; h[2] = prev[2]; h[3] = prev[3];
- h[4] = prev[4]; h[5] = prev[5]; h[6] = prev[6]; h[7] = prev[7];
- h[8] = prev[8]; h[9] = prev[9]; h[10] = prev[10]; h[11] = prev[11];
- h[12] = prev[12]; h[13] = prev[13];
-
- carry = h[p];
- h[p] = 0; /*disp*/
-
- while (carry-->0)
- {
- p++;
- if (p==13) p=0;
- h[p] += 1; /*disp*/
- }
- if (p < 6 && h[p] == 1)
- {
- h[p] = 0; /*disp*/
- h[6] += 1; /*disp*/
- temp = h[12-p];
- h[12-p] = 0; /*disp*/
- h[6] += temp; /*disp*/
- }
- if (h[0]==0 && h[1]==0 && h[2]==0 && h[3]==0 && h[4]==0 && h[5]==0)
- {
- for (i=7; i<13; i++)
- {
- temp = h[i];
- h[i] = 0; /*disp*/
- h[6] += temp; /*disp*/
- }
- return OVER;
- }
- else if (h[7]==0 && h[8]==0 && h[9]==0 && h[10]==0 && h[11]==0 && h[12]==0)
- {
- for (i=0; i<6; i++)
- {
- temp = h[i];
- h[i] = 0; /*disp*/
- h[6] += temp; /*disp*/
- }
- return OVER;
- }
- else
- {
- if (p==6)
- return MY;
- else
- return YOUR;
- }
- }
-
-
-